package DP;

/**
 * @author 曹见朋
 * @create 2024-06-12-23:21
 */
public class Main474 {
    // TODO 474. 一和零
    public static int findMaxForm(String[] strs, int m, int n) {

        int[][] dp = new int[m + 1][n + 1];

        dp[0][0] = 0;
        for(String str : strs){
            int x = 0;
            int y = 0;
            for(char c : str.toCharArray()){
                if(c == 48) x++;
                if(y == 49) y++;
            }

            for(int i = m; i >= x; i--){
                for(int j = n; j >= y; j--){
                    dp[i][j] = Math.max(dp[i][j], dp[i - x][j - y] + 1);
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        String[] strs = new String[]{"10", "0001", "111001", "1", "0"};
        int m = 5;
        int n = 3;
        int maxForm = findMaxForm(strs, m, n);
        System.out.println(maxForm);

    }
}
